Given a communications network comprising multiple network devices, it is a problem to set up secure connections between pairs of such network devices. One way to achieve this is described in C. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro and M. Yung, “Perfectly-Secure Key distribution for Dynamic Conferences”, Springer Lecture Notes in Mathematics, Vol. 740, pp. 471-486, 1993 (referred to as ‘Blundo’).
It assumes a central authority, also referred to as the network authority or as the Trusted Third Party (TTP), that generates a symmetric bivariate polynomial f(x,y), with coefficients in the finite field F with p elements, wherein p is a prime number or a power of a prime number. Each device has an identity number in F and is provided with local key material by the TTP. For a device with identifier η, the local key material are the coefficients of the polynomial f(η,y).
If a device η wishes to communicate with device η′, it uses its key material to generate the key K(η, η)=f(η, η′). As f is symmetric, the same key is generated.
A problem of this key sharing scheme occurs if an attacker knows the key material of t+1 or more devices, wherein t is the degree of the bivariate polynomial. The attacker can then reconstruct the polynomial f(x,y). At that moment the security of the system is completely broken. Given the identity numbers of any two devices, the attacker can reconstruct the key shared between this pair of devices.
Reference is made to the paper “A Permutation-Based Multi-Polynomial Scheme for Pairwise Key Establishment in Sensor Networks” by authors Song Guo, Victor Leung, and Zhuzhong Qian, IEEE International Conference on Communications, 2010. It presents a permutation-based multi-polynomial scheme for pairwise key establishment in wireless sensor networks. Different from Blundo, the scheme presented in Song does not give each node just one share of a symmetric polynomial, but a group of permuted shares.